Năm 209 TCN, Trần Thắng khởi nghĩa ở Đại Trạch chống lại nhà Tần, lực lượng phát triển mạnh, không lâu sau xưng làm Trương Sở Vương. Lưu Bang hưởng ứng, dấy binh ở huyện Bái. Phàn Khoái cùng Tiêu Hà và Tào Tham đi theo Lưu Bang. Ông đứng dưới cờ làm chức xá nhân.

Phàn Khoái có sức khoẻ lại dũng cảm hơn người, luôn đi bên cạnh Lưu Bang. Trong nhiều trận chiến ác liệt, ông đều hăng hái chiến đấu, giết được nhiều địch.

Trận đánh với tướng Tần là Tư Mã Ni ở nước Sở, ông một mình chém 15 quân địch, đánh lui quân Tần, được phong làm Quốc đại phu. Trận đánh Thành Dương và thắng Lý Do (con Lý Tư), ông chém được 16 đầu, được phong tước Thượng giám. Sau đó vây đánh Đông Quận, ông chém 14 quân địch, bắt sống 11 người, được phong làm Ngũ đại phu[2].

Phàn Khoái tham gia đại phá tướng Tần là Dương Hùng đồn trú ở Hy Giám, được phong làm Hiền Thành quân. Năm 206 TCN, Lưu Bang tiến vào Quan Trung, ông xung phong trận, chém 1 đô uý, 10 lính và bắt sống 140 quân Tần[3].

Lưu Bang vào Hàm Dương, tiêu diệt nhà Tần. Theo như lời ước của Sở Hoài vương khi chia quân đi đánh Tần: "Ai vào Quan Trung trước thì được làm vua", đáng lý ngôi vua ở Quan Trung thuộc về Lưu Bang, nhưng Hạng Vũ có binh lực mạnh hơn, lấn át Lưu Bang nên khi nghe tin Hạng Vũ tiến vào Quan Trung, Lưu Bang phải lui ra Bá Thượng.